package com.learning.algorithm.sort.divideAndConquer;

import com.learning.algorithm.sort.ArraysUtil;
import com.learning.algorithm.sort.CheckSort;
import com.learning.algorithm.sort.IntArraySort;
import com.learning.algorithm.sort.simpleSort.SelectSort;

import java.util.Arrays;

/**
 * @Author: lishi
 * @Description: 快速排序
 * @Date: 2021/11/23 15:13
 */
public class QuickSort implements IntArraySort {
    public static int[] quickSort(int[] arrays) {
        return childSort(arrays);
    }

    private static int[] childSort(int[] arrays) {
        if (arrays.length <= 2) {
            SelectSort.selectSort(arrays);
            return arrays;
        }
        int separatorPos = 0;
        int endPos = arrays.length - 1;
        int startPos = 0;
        while (endPos > startPos) {
            for (; endPos > startPos; endPos--) {
                if (arrays[endPos] < arrays[separatorPos]) {
                    ArraysUtil.swap(arrays, endPos, separatorPos);
                    separatorPos = endPos;
                    break;
                }
            }

            for (; startPos < endPos; startPos++) {
                if (arrays[startPos] > arrays[separatorPos]) {
                    ArraysUtil.swap(arrays, startPos, separatorPos);
                    separatorPos = startPos;
                    break;
                }
            }
        }
        int[] leftArrays = new int[separatorPos];
        int[] rightArrays = new int[arrays.length - separatorPos - 1];
        System.arraycopy(arrays, 0, leftArrays, 0, separatorPos);
        System.arraycopy(arrays, separatorPos + 1, rightArrays, 0, arrays.length - separatorPos - 1);
        rightArrays = childSort(rightArrays);
        leftArrays = childSort(leftArrays);

        System.arraycopy(leftArrays, 0, arrays, 0, separatorPos);
        System.arraycopy(rightArrays, 0, arrays, separatorPos + 1, arrays.length - separatorPos - 1);

        return arrays;
    }

    public String getDesc() {
        return "快速排序";
    }

    public int[] sort(int[] arrays) {
        return quickSort(arrays);
    }

    public static void main(String[] args) {
        int length = 100;
        int[] originArrays = ArraysUtil.genNoDuplicateIntArray(length);
        int[] cloneArrays = new int[length];
        System.arraycopy(originArrays, 0, cloneArrays, 0, length);
        cloneArrays = quickSort(cloneArrays);
        System.out.println(Arrays.toString(originArrays));
        System.out.println(Arrays.toString(cloneArrays));
        System.out.println(CheckSort.checkSortResult(originArrays, cloneArrays));
    }
}
